\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{listings}

\lstset{
language=MATLAB,                % choose the language of the code
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,                   % adds a frame around the code
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
}

\title{Decision Theory I: Assignment 1} 
\author{Yifan Tong, yt347} 
\date{September 23th, 2010}

\begin{document} 
\maketitle 
\newpage
\section{Problem 1} % (fold)
\label{sec:problem_1}
Given $\{x, y, z\}$\\
If $x \succ y, y \succ z$, \\
We have $y \not\succ x, z \not\succ y$ by asymmetry\\
From the above, we derive that $z \not\succ x$ by negative transitivy\\
$z \not\succ x$ implies that $x \succ z$ or $ x = z $ \newline
if $x = z$, then $x \succ z$ and $y \succ z$ form a contradiction\\
$\therefore z \not\succ x \rightarrow x \succ z$\newline
$\therefore x \succ y, y \succ z \rightarrow x \succ z$ Q.E.D.\\
% section problem_1 (end)

\section{Problem 2} % (fold)
\label{sec:problem_2}
Given:
\begin{itemize}
\item $C(\{x, y\}) = \{x\}$
\item $C(\{y, z\}) = \{y\}$
\item $C(\{x, z\}) = \{z\}$
\end{itemize}
Select two sets: $\{x, y\}, \{y, z\}$\\
\indent $C(\{x, y\}, \{y, z\})=
C(\{x, y, z\}) =
\{x, y\}$\\
By Sen's $\alpha$,\newline
\indent $C(\{x, y\}) = \{x, y\}$, \\
But $C(\{x, y\}) = \{x\}$\\
$\therefore$ we have a contradiction
% section problem_2 (end)

\section{Problem 20} % (fold)
\label{sec:problem_20}
\textbf{\underline{Algorithm to Find Maximum-Size Half-Integral Matching}}:
$H$ contains 2 matchings, each of which is of cost 3:
\begin{itemize}
  \item $M_{1} = \{(a,b),(c,d),(e,f)\}$
  \item $M_{1} = \{(b,c),(d,e),(f,a)\}$
\end{itemize}
However, $G$ contains one other matching, $M_{3} = \{(c,b),(d,a),(e,f)\}$, not a subgraph of $H$ which is of cost 2.5. Thus, $M_{3}$, being the only other perfect matching, is the minimum-cost perfect matching. And therefore, $M_{1}$ and $M_{2}$, the only 1-factor subgraphs of $H$, are not minimum-cost perfect matchings.\newline
$\therefore$ the statement is false.
\begin{itemize}
  \item For every edge $(u, v)$ in $G$, we create two edges $(u^{+}, v^{-})$ and $(u^{-}, v^{+})$ in $G^{+} \cup G^{-}$ (referred to as $G^{+-}$ from this point onward), and we label all edges in $G^{+-}$ with the same weight.  The resulting graph is an unweighted bipartite.  This process can be done in $O(m)$.
  \item We run the Hopcroft-Karp algorithm on graph $G^{+-}$, and this gives us the maximum matching, $M$, for $G^{+-}$.  This step can be done in $O(m\sqrt{n})$.
  \item We create another graph $H(V, \emptyset)$ with the vertices found in $G$ and convert the matching found on $G^{+-}$ back to graph $H$. For every edge in $G^{+-}$, we connect the corresponding vertices in $H$, and label the edge with a weight of $\frac{1}{2}$.  For example, in the case of $(u^{+}, v^{-})$ and $(u^{-}, v^{+})$, we create two edges of weight $\frac{1}{2}$ between $u$ and $v$ in $H$. The resulting graph $H$ is a \emph{two-fact}. This process can be done in $O(m)$, since there are at most $m$ edges in $M$.
  \item Optionally, combine edges with weight $\frac{1}{2}$ to form edges of weight $1$.
\end{itemize}
% section problem_20(end)
\end{document}
